#coding=utf-8
from sparse import sparse

x = 0
y = 0
z = 0

class Location(object):
    def __init__(self, x, y):
        self.x = x
        self.y = y
    
    def __repr__(self):
        return "(%i:%i)"%(self.x, self.y)    
    __str__ = __repr__
    
class Node(object):
    def __init__(self, word, parent=None):
        self.word = word
        self.parent = parent
        self.children = []
        
    def __repr__(self):
        if hasattr(self, 'location'):
            return "%s %s"%(self.location, self.word)
        return self.word
    __str__ = __repr__
        
    def add_child(self, child):
        self.children.append(child)
    
    def mark_number(self):
        global x,y
        
        self.location = Location(x, y)
        
        if not self.children:return
        
        x = x + 1
        y = y - 1
        
        for child in self.children:
            y = y + 1
            child.mark_number()
            
            
        x = self.location.x
        #print x,y
        
    def mark_number2(self):
        global z
        self.z = z
        if not self.children:return
        
        for child in self.children:
            z = z + 1
            child.mark_number2()
    
    
